package DecisionTree;



import java.io.*;
import java.util.Random;


/**
 * Decision tree algorithm
 * @author Michal
 *
 */
public class DecisionTree {
    
    static BufferedReader    keyboardInput = new BufferedReader(new InputStreamReader(System.in));
    Node rootNode = null;
   
    public DecisionTree(Node root){
    	rootNode = root;
    }
    
    /**
     * Organizes nodes and displays connections
     * @param existingNodeID
     * @param newNodeID
     * @param val
     */
    public void addTrueNode(int existingNodeID, int newNodeID, boolean val) {
		// If no root node do nothing		
		if (rootNode == null) 
		    return;
		
		// Search tree		
		if (searchTreeAndAddTrueNode(rootNode,existingNodeID,newNodeID, val)) {
		    System.out.println("Added node " + newNodeID + " onto \"true\" branch of node " + existingNodeID);
		}
		else 
			System.out.println("Node " + existingNodeID + " not found");
	}

    
    /**
     * Searches tree and adds true node into appropriate position
     * @param currentNode
     * @param existingNodeID
     * @param newNodeID
     * @param val
     * @return
     */
    private boolean searchTreeAndAddTrueNode(Node currentNode, int existingNodeID, int newNodeID, boolean val) {
    	
    	if (currentNode.id == existingNodeID) {
		    // Found node
		    if (currentNode.trueBranch == null) 
		    	currentNode.trueBranch = new Node(newNodeID, val);
		    else {
		        System.out.println("WARNING: Overwriting previous node " + "(id = " + currentNode.trueBranch.id +
		        		") linked to true branch of node " + existingNodeID);
		        currentNode.trueBranch = new Node(newNodeID, val);
			}		
    	    return(true);
	    }
    	else {
		    // Try true branch if it exists
		    if (currentNode.trueBranch != null) { 	
		        if (searchTreeAndAddTrueNode(currentNode.trueBranch,existingNodeID,newNodeID, val)) {    	
		            return(true);
			    }	
			else {
	    	        // Try false branch if it exists
		    	    if (currentNode.falseBranch != null) {
	    	    		return(searchTreeAndAddTrueNode(currentNode.falseBranch, existingNodeID,newNodeID, val));
				}
			    else
			    	return(false);	// Not found here
			    }
	    	}
		    return(false);		// Not found here
	    }
   	} 	
    		
    /**
     * Adds false node and displays connections
     * @param existingNodeID
     * @param newNodeID
     * @param val
     */
    public void addFalseNode(int existingNodeID, int newNodeID, boolean val) {
	
	if (rootNode == null) 
	     return;
	
	if (searchTreeAndAddFalseNode(rootNode,existingNodeID,newNodeID,val)) {
	    System.out.println("Added node " + newNodeID + " onto \"false\" branch of node " + existingNodeID);
	}
	else 
		System.out.println("Node " + existingNodeID + " not found");
	}
	
    /**
     * Searches tree and puts false node into appropriate place
     * @param currentNode
     * @param existingNodeID
     * @param newNodeID
     * @param val
     * @return
     */
    private boolean searchTreeAndAddFalseNode(Node currentNode, int existingNodeID, int newNodeID, boolean val) {
    	if (currentNode.id == existingNodeID) {
		    // Found node
		    if (currentNode.falseBranch == null) 
		    	currentNode.falseBranch = new Node(newNodeID,val);
		    else {
		        System.out.println("WARNING: Overwriting previous node " + "(id = " + currentNode.falseBranch.id +
				") linked to true branch of node " + existingNodeID);
		        currentNode.falseBranch = new Node(newNodeID,val);
			}		
    	    return(true);
	    }
		else {
		    // Try true branch if it exists
		    if (currentNode.trueBranch != null) { 	
		        if (searchTreeAndAddFalseNode(currentNode.trueBranch, existingNodeID,newNodeID,val)) {    	
		            return(true);
			    }	
				else {
		    	        // Try no branch if it exists
			    	    if (currentNode.falseBranch != null) {
		    	    		return(searchTreeAndAddFalseNode(currentNode.falseBranch, existingNodeID,newNodeID,val));
					}
				    else return(false);	// Not found here
				 }
			}
		    else
		    	return(false);	// Not found here
		}
   	} 	


  

    /**
     * Queries tree and generates 'questions" with values (randomizes path)
     * @param currentNode
     * @throws IOException
     */
    public void queryBinTree(Node currentNode) throws IOException {
        // Test for leaf node (answer) and missing branches
        if (currentNode.trueBranch==null || currentNode.falseBranch==null) {
            return;
        }
        
        askQuestion(currentNode);
    }

    /**
     * Responsible for generating random path
     * @param currentNode
     * @throws IOException
     */
    private void askQuestion(Node currentNode) throws IOException {
        Random rand = new Random();        
    	boolean value = rand.nextBoolean();
        if (value) 
        	queryBinTree(currentNode.trueBranch);
        else 
        	queryBinTree(currentNode.falseBranch);  
    }
    


    public void outputBinTree(String tag, Node currentNode) {
    	
        // Check for empty node
        if (currentNode == null) 
        	return;

        // Output
        System.out.println("[" + tag + "] nodeID = " + currentNode.id + ", value = " + currentNode.value);
        		
        // Go down yes branch
        outputBinTree(tag + ".1",currentNode.trueBranch);

        // Go down no branch
        outputBinTree(tag + ".2",currentNode.falseBranch);
        
	}      		
 
}
